package J.算法.动态规划;

public class _面试题1716按摩师 {
    //穷举求极值
    //base case:nums.lenth =0 时 return0
    //状态 ：来的第i个请求
    //状态转移：
    public int massage(int[] nums) {

        if (nums.length ==0){
            return 0;
        }
        if (nums.length==1){
            return nums[0];
        }

        int[] dp = new int[nums.length+1];

        dp[0]=nums[0];
        dp[1]= Math.max(nums[0],nums[1]);


        for (int i = 2; i <= nums.length; i++) {

            dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);

        }

        return dp[nums.length];

    }
    /**
     * 空间优化：只跟三个数字有关 所以数组长度固定3 存数值的时候取模操作
     */
    public int massage1(int[] nums) {

        if (nums.length ==0){
            return 0;
        }
        if (nums.length==1){
            return nums[0];
        }

        int[] dp = new int[3];

        dp[0]=nums[0];
        dp[1]= Math.max(nums[0],nums[1]);


        for (int i = 2; i < nums.length; i++) {

            dp[i % 3] = Math.max(dp[(i-2) % 3]+nums[i],dp[(i-1) % 3]);

        }

        return dp[(nums.length-1) % 3];

    }
}
